#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<int> temp;
        vector<vector<int>> res;
        vector<int> book(nums.size(), 0);
        // 利用排序去重和优化
        sort(nums.begin(), nums.end());
        function<void(int)> func([&](int pos) -> void
                                 {
            if(pos==nums.size()){
                res.push_back(temp);
                return;
            }
            for(int i=0;i<nums.size();i++){
                if(book[i]||i>0&&nums[i]==nums[i-1]&&book[i-1])
                    continue;
                //去重: 观察执行顺序如果这个数跟上一个一样,上一个还没在这轮出现过
                //     说明已经在上轮出现过了
                temp.push_back(nums[i]);
                ++book[i];
                func(pos+1);
                temp.pop_back();
                --book[i];
            } });
        func(0);
        return res;
    }
};